package design;

import java.util.ArrayList;
import java.util.List;
import java.util.Random;

/**
 * @author pengfei.hpf
 * @date 2020/3/25
 * @verdion 1.0.0
 * 528. 按权重随机选择
 * 给定一个正整数数组 w ，其中 w[i] 代表位置 i 的权重，请写一个函数 pickIndex ，它可以随机地获取位置 i，选取位置 i 的概率与 w[i] 成正比。
 *
 * 说明:
 *
 * 1 <= w.length <= 10000
 * 1 <= w[i] <= 10^5
 * pickIndex 将被调用不超过 10000 次
 * 示例1:
 *
 * 输入:
 * ["Solution","pickIndex"]
 * [[[1]],[]]
 * 输出: [null,0]
 * 示例2:
 *
 * 输入:
 * ["Solution","pickIndex","pickIndex","pickIndex","pickIndex","pickIndex"]
 * [[[1,3]],[],[],[],[],[]]
 * 输出: [null,0,1,1,1,0]
 * 输入语法说明：
 *
 * 输入是两个列表：调用成员函数名和调用的参数。Solution 的构造函数有一个参数，即数组 w。pickIndex 没有参数。输入参数是一个列表，即使参数为空，也会输入一个 [] 空列表。
 */
public class RandomPickWithWeight {
    List<Integer> list;
    int total;
    Random random;

    public RandomPickWithWeight(int[] w) {
        list = new ArrayList<>();
        total = 0;
        random = new Random();
        for(int i: w){
            total += i;
            list.add(total);
        }
    }

    //TODO: 参考一下这个思想
    public int pickIndex() {
        int i = random.nextInt(total);
        int l = 0;
        int r = list.size();
        while(l != r){
            int m = (l + r)/2;
            if(i >= list.get(m)){
                l = m + 1;
            } else {
                r = m;
            }
        }
        return l;
    }
}
